Many enterprises are moving toward adoption of cloud-based services. For many enterprises, middleboxes are one of the important components of the enterprise network. Accordingly, several cloud providers and third party services providers are offering middleboxes as a service (or as a virtual appliance) within the cloud. One type of middlebox that is commonly used is the Wide Area Network (WAN) optimizer middlebox (which also may be referred to as a Redundancy Elimination (RE) middlebox, given that WAN optimization typically includes RE functions). In general, WAN optimizer middleboxes suppress duplicate content within traffic, and also may provide bandwidth savings as well as improve application performance. A WAN optimizer middlebox of an enterprise can be deployed between the enterprise and the cloud, or between two cloud sites used by the enterprise in a distributed setting. In many cases, it is desirable to have pay-per-use capabilities for such WAN optimizer middleboxes, similar to applications like web servers, where the providers or users of the WAN optimizer middleboxes incur costs as per traffic demand. As the adoption of cloud-based services by enterprises continues to grow, it is becoming desirable to be able to scale WAN optimizer middleboxes to handle greater volumes of traffic.